At the heart of most topics in theoretical physics is a variational principle. Given the phase space of a system, i.e. the space of possible configuration and momentum variables, the dynamics of the system is contained in the definition of the action. The action is a functional on phase space, and the equations of motion are obtained from it by the condition that the path in phase space which the system follows corresponds to an extremum of the action. All the fundamental classical theories like mechanics, thermodynamics, electromagnetism and general relativity are conveniently defined in terms of the action. In fact, given the action one can often construct the corresponding quantum theory straight-forwardly with so called path-integrals. All this we only point out to emphasize how fundamental extremization procedures are in physics.
Monte Carlo methods have their origin in an anology with statistical physics. A statistical system consists typically of a large number of particles, and we are interested in its configuration, say the position and velocity of the particles, and in how it evolves in time. Key aspect of the evolution is that some quantity like the action or the energy is minimized. Let us give a concrete example. Consider a metal near its transition from a liquid to a solid state. A configuration is described by giving the position and velocity of each atom in the metal. The atoms do not move around freely but experience forces due to the combined electric potential created by all atoms. At high enough temperatures, the atoms move around quite randomly, but as the metal is cooled, the atoms move less, and when the metal becomes solid, the atoms are essentially fixed in place by their mutual electromagnetic forces. This process is called annealing. The energetically most favourable configuration for the solid state is that of a regular, crystalline structure.
The surprising fact is that in experiments nature is able to come extremely close to this minimum in energy, i.e. billions of atoms form a perfectly regular lattice — if enough time is allowed for the cooling process. Imagine the atoms moving around in the electric potential like balls on a surface with many dents and bumps. At the minimal energy every atom/ball has come to rest at a place where the potential has a local minimum. If the atoms are slowed down too quickly, however, they probably have not found the smallest local minima possible, i.e. the metal solidifies in a less regular, amorphous state in which the total potential energy is larger than in a crystal.
In Monte Carlo simulations one simulates the evolution of a statistical system on a computer [5]. One does not attempt to solve the terribly complicated equations of motion for each particle exactly, but follows a probabilistic evolution that stays close to but not exactly at the minimum of the action. First of all, one chooses a suitable description of all possible system configurations. Second, one needs a set of elementary moves which are ergodic, that is, changes in the configurations which enable one to cover the space of all configurations step by step. Third, for a given configuration moves are suggested completely randomly. Finally, the physically correct evolution is approximated by accepting a suggested random move with a probability that depends on whether the move increases or decreases the action.
So let us give an example for what these probabilities should be for a system in thermal equilibrium. In this case the temperature is the same everywhere and the energy is constant. Notice that even if the total energy or the temperature is fixed, individual particles may behave differently. In many cases the probability p(E) that a single particle has energy E when the system is in thermal equilibrium at temperature T is given by the Boltzmann probability distribution,
| p(E)∼exp(- E/kT), | (1) |
Simulated annealing is special in that 'cooling' is introduced [2]. The temperature is lowered towards 0, and in that limit moves that raise the energy are almost never accepted by the Metropolis algorithm. Again, if the system is cooled very slowly so that it is effectively always in thermal equilibrium, the system is also close to its minimal energy. If cooling happens too quickly, many particles are caught after moves away from the minimum and the total energy is not minimal. What we have to add to the prescription for Monte Carlo simulations of systems in thermal equilibrium is an ``annealing schedule'' which defines how fast the temperature is lowered.
Let us end our discussion of physical systems at this point. Monte Carlo simulations are widely and successfully used in the physics of statistical systems. They are that successful, in fact, that non-statistical theories like QCD (quantum chromo dynamics), the theory of elementary particles, has been turned into a statistical theory to make it tractable. In the context of physics let us mention that the idea of influence potentials has already been applied successfully in go [1,6].